#leetcode题目207：课程表
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n)
#方法：拓扑排序,优先搜索

#一般来说，这种拓扑结构的一般都是优先考虑深度优先还是广度优先。

#深度优先：

#广度优先：
#构建有向无环图，实现广度搜索。


from typing import List
from collections import defaultdict, deque
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        """
        课程表
        你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
        在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，
        其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
        例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
        请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
        """
        # 初始化入度数组，courses[i] 表示课程i的入度（前置课程数量）
        courses = [0] * numCourses
        
        # 构建邻接表，needUnlock[prerequisite] = [courses that depend on this prerequisite]
        needUnlock = defaultdict(list)
        
        # 构建图和入度数组
        for pair in prerequisites:
            target = pair[0]  # 目标课程
            need = pair[1]    # 前置课程
            
            # 将目标课程添加到前置课程的依赖列表中
            needUnlock[need].append(target)
            
            # 增加目标课程的入度
            courses[target] += 1
        
        # 初始化队列，将所有入度为0的课程加入队列
        queue = deque()
        for i in range(numCourses):
            if courses[i] == 0:
                queue.append(i)

        # 初始化队列，将所有入度为0的课程加入队列
        queue = deque()
        for i in range(numCourses):
            if courses[i] == 0:
                queue.append(i)
        
        # BFS拓扑排序
        while queue:
            # 取出一个入度为0的课程
            c = queue.popleft()
            
            # 如果这个课程是其他课程的前置课程
            if c in needUnlock:
                # 遍历所有依赖这个课程的课程
                for dependent_course in needUnlock[c]:
                    # 减少依赖课程的入度
                    if courses[dependent_course] > 0:
                        courses[dependent_course] -= 1
                        
                        # 如果依赖课程的入度变为0，加入队列
                        if courses[dependent_course] == 0:
                            queue.append(dependent_course)
                
                # 处理完后移除这个课程
                del needUnlock[c]
        
        # 检查是否所有课程的入度都为0
        for c in courses:
            if c > 0:
                return False
        
        return True


#测试数据
numCourses = 2
prerequisites = [[1,0]]
#预期输出：true
solution = Solution()
print(solution.canFinish(numCourses, prerequisites))


numCourses = 2
prerequisites = [[1,0],[0,1]]
#预期输出：false
solution = Solution()
print(solution.canFinish(numCourses, prerequisites))
